public class Main {
    public static void main(String[] args) {
        System.out.println(new Solution().longestPalindromeSubseq1("bbbab"));
        System.out.println(new Solution().longestPalindromeSubseq1("cbbd"));
        System.out.println(new Solution().longestPalindromeSubseq1("aa"));
    }
}

class Solution {
    //动态规划，从两端往里遍历
    public int longestPalindromeSubseq(String s) {
        if (s.length() == 1) {
            return 1;
        }
        int[][] dp = new int[s.length() + 2][s.length() + 2];
        if (s.charAt(0) == s.charAt(s.length() - 1)) {
            dp[1][s.length()] = 2;
        }

        int ans = dp[1][s.length()];
        for (int l = s.length() - 1; l >= 1; l--) {
            for (int i = 1; i + l - 1 <= s.length(); i++) {
                if (l == 1) {
                    dp[i][i] = dp[i - 1][i + 1] + 1;
                    ans = Math.max(ans, dp[i][i]);
                    continue;
                }
                int j = i + l - 1;
                char ci = s.charAt(i - 1), cj = s.charAt(j - 1);
                if (ci == cj) {
                    dp[i][j] = dp[i - 1][j + 1] + 2;
                    ans = Math.max(ans, dp[i][j]);
                    continue;
                }
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j + 1]);
            }
        }
        return ans;
    }

    //动态规划，从一点向两端遍历
    public int longestPalindromeSubseq1(String s) {
        int[][] dp = new int[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = 1;
            if (i < s.length() - 1) {
                dp[i][i + 1] = s.charAt(i) == s.charAt(i + 1) ? 2 : dp[i][i];
            }
        }

        for (int l = 3; l <= s.length(); l++) {
            for (int i = 0; i + l - 1 < s.length(); i++) {
                int j = i + l - 1;
                char ci = s.charAt(i), cj = s.charAt(j);
                if (ci == cj) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[0][s.length() - 1];
    }
}